#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>

//struct c
//{
//	int num;
//	int con;
//}a[16];
//int main()
//{
//	for (int i = 0; i < 8; i++)
//	{
//		scanf("%d", &a[i].num);
//		a[i].con = 0;
//	}
//	for (int i = 8 - 1; i >= 1; i--)
//	{
//		for (int j = i - 1; j >= 0; j--)
//		{
//			if (a[i].num < a[j].num)
//			{
//				a[i].con++;
//
//			}
//			else
//			{
//				a[j].con++;
//
//			}
//		} 
//	}
//	for (int i = 0; i < 8; i++)
//	{
//		printf("%d %d\n", a[i].num, a[i].con);
//	}
//	return 0;
//}\

//int main()
//{
//	union MyUnion
//	{
//		struct
//		{
//			int x;
//			int y;
//		}in;
//		int a;
//		int b;
//	}e;
//	e.a = 1;
//	e.b = 2;
//	e.in.x = e.a * e.b;
//	e.in.y = e.a + e.b;
//	printf("%d %d\n", e.in.x, e.in.y);
//	return 0;
//}

void print(int arr[], int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b; 
	*b = tmp;
}

void bubble_sort(int arr[], int sz)
{
	int flag = 0;
	for (int i = 0; i < sz - 1; i++)
	{
		for (int j = 0; j < sz - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				flag = 1;
				swap(&arr[j], &arr[j + 1]);
			}
		}
		if (!flag)
		{
			break;
		}
	}
}

void select_sort(int arr[], int sz)
{
	for (int i = 0; i < sz - 1; i++)
	{
		int tmp = i;
		for (int j = i + 1; j < sz; j++)
		{
			if (arr[j] < arr[tmp])
			{
				tmp = j;
			}
		}
		if (tmp != i)
		{
			swap(&arr[i], &arr[tmp]);
		}
	}
}

void double_bubble_sort(int arr[], int sz)
{
	int left = 0;
	int right = sz - 1;
	while (left < right)
	{
		for (int i = left; i < right; i++)
		{
			if (arr[i] > arr[i + 1])
			{
				swap(&arr[i], &arr[i + 1]);
			}
		}
		right--;
		for (int i = right; i > left; i--)
		{
			if (arr[i] < arr[i - 1])
			{
				swap(&arr[i], &arr[i - 1]);
			}
		}
		left++;
	}
}

void insert_sort(int arr[], int sz)
{
	for (int i = 1; i < sz; i++)
	{
		int tmp = arr[i];
		int j = i-1;
		while (j >= 0 && tmp < arr[j])
		{
			arr[j+1] = arr[j];
			j--;
		}
		arr[j + 1] = tmp;
	}
}

int main()
{
	int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	print(arr, sz);
	//bubble_sort(arr, sz);
	//select_sort(arr, sz);
	//double_bubble_sort(arr, sz);
	insert_sort(arr, sz);
	print(arr, sz);

	return 0;
}